The present embodiments relate to electronic devices and circuits and are more particularly directed to such devices and circuits that include a first-in first-out (“FIFO”) memory system with a single bit indication of an addressed word location in the FIFO.
Electronic circuits are prevalent in numerous applications, including those used in personal, business, and other devices. Demands of the marketplace affect many aspects of the design of these circuits, including factors such as device complexity, size, and cost. Various of these electronic circuits include some aspect of digital signal processing and, quite often, these circuits include storage devices that operate on a FIFO basis. As is well-known in the art, such FIFO circuits are so named because data words are read from the circuit in the same order as they were written to the circuit. As a storage device, the FIFO is also sometimes referred to as a FIFO memory or as a FIFO random access memory (“RAM”). Typically, a FIFO is a logical array for storing a number of data words. The size of each data word in the FIFO depends on the application and may be any number of bits, where 4 bits, 8 bits, 16 bits, and 32 bits are common examples, while any number of bits per word may be implemented based on the application.
A FIFO has a number of word storage locations, and typically in the prior art any of these locations may be indicated, or “addressed,” during operation of the FIFO by both a read pointer and a write pointer. Typically, the read pointer indicates the word storage location from which a next word will be read, and the write pointer indicates the word storage location into which a next word will be written. The number of word storage locations in a given FIFO also is typically dictated at least in part by the application. In view of that application, the FIFO design is often determined in an effort to satisfy data requirements while minimizing this number of storage locations so as to avoid unnecessarily enlarging the FIFO. Typically, however, with the designed minimized number of word storage locations, there is an expectation that the pointers may at some instance point to a same word storage location, which in the art is referred to as a collision. When a collision occurs, often an interrupt or the like is generated, because in this condition there is the possibility of an imminent data corrupting action. For example, in a FIFO having word storage locations 0 through Z, if a word has been written into location 0 and the write pointer then points to location 1, consider next that a read occurs of the word at location 0 and the read pointer then also points to location 1. Thus, both pointers point to the same FIFO location. Without any additional action, if the next FIFO operation is a read, then the data read will be at a location that has not yet been written, thereby providing invalid data for the read. As a result, this collision must be detected so as to warn, or prevent, the system from relying on invalid data. As another example in that same FIFO, if Z words have been written into locations 0 through Z of that same FIFO and the write pointer then wraps around to location 0 without any read occurring, then again both pointers point to the same FIFO location. Without any additional action, if the next FIFO operation is a write, then the valid data at location 0, which has not yet been read, will be overwritten. Thus, this collision also must be detected.
In an effort to respond to pointer collisions in a FIFO, the prior art has developed various systems based on monitoring the read and write pointers relative to one another. In these systems, the prior art pointers are typically multiple-bit digital values that numerically identify each word storage location. For example, for the above instance of a FIFO with locations 0 through Z=2N−1, then both the read pointer and the write pointer consist of incrementing modulo counters with N bits that increment through the values of 0 through 2N−1 and then start once more at 0 (or vice versa for decrementing counters). Often each such counter is referred to as a pointer vector in that each such vector has multiple bits, where at least one of those multiple bits, by definition, is a different value for each of the 2N different addresses of the FIFO. Given this implementation of pointers, the prior art manner of detecting collisions typically compares the two pointers, where a collision is detected if the pointers have the same counter values. The comparison may be implemented using arithmetic computations such as through use of a comparator or subtracting unit, by ways of example. However, the present inventors have observed that in certain FIFOs, and particularly in asynchronous FIFOs, these techniques may become quite extensive. Specifically, in asynchronous FIFOs, a read may occur according to one tiling domain that is independent of when a write may occur, that is, the read and write operations, and pointers, are asynchronous with respect to one another. As a result, as a necessary element of the pointer comparison technique described above, the prior art also involves a complex manner of taking the value of one pointer into the clock domain of the other pointer so as to provide an accurate comparison of the two to avoid metastability problems. In other words, without such an action, by time a first pointer (e.g., read) is copied and compared to a second pointer (e.g., write), the first pointer may be in the process of changing; further, since each pointer address is represented by a vector, and if that vector is changing at the time it is copied, then some bits in the vector may contain the value before the change while others contain the new value. In this case, the captured vector value would not just be either the previous value or the new value but some totally unknown address instead. Thus, the prior art includes additional circuitry for attempting to accommodate this necessary crossing over of one pointer into the other pointer's time domain. This additional circuitry adds complexity, which consequently increases device size, cost, and power consumption, all of which are undesirable in circuit design, particularly in today's competitive marketplace.
In view of the above, the preferred embodiments as set forth below seek to improve upon the prior art as well as its associated drawbacks.